package com.example.demo.leetcode100题;

import com.example.demo.StopWatchTemplate;
import java.util.HashMap;

/**
 * @author：zzc
 * @date: 2022/8/30
 */
public class 爬楼梯 {

    //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    //每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    //注意：给定 n 是一个正整数。
    //示例 1：
    //输入： 2
    //输出： 2
    //解释： 有两种方法可以爬到楼顶。
    //1. 1 阶 + 1 阶
    //2. 2 阶
    //示例 2：
    //输入： 3
    //输出： 3
    //解释： 有三种方法可以爬到楼顶。
    //1. 1 阶 + 1 阶 + 1 阶
    //2. 1 阶 + 2 阶
    //3. 2 阶 + 1 阶

    private static int palouti(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return palouti(n - 1) + palouti(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(StopWatchTemplate.doSupplier(() -> palouti(30)));
    }


    // 上面的存在重复计算的问题
    private static int palouti2(int n) {
        HashMap<Integer, Integer> hashMap = new HashMap();
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (hashMap.get(n) != null) {
            return hashMap.get(n);
        } else {
            int i = palouti2(n - 1) + palouti2(n - 2);
            hashMap.put(n, i);
            return i;
        }

    }


}
